“P “VIS A VIS “NP ” CONCATENATED WITH “NPC” AND CONCOMITANT “NP(HARD)”PROBLEM –

problem. While many may have heard of the P vs. NP problem in computational science through pop culture references (The Simpsons, Futurama) few understand its importance to modern computing, or what quantum computing may mean in relation to it. In computational complexity theory, P and NP are two classes of problems. P is the class of decision problems that a deterministic Turing machine can solve in polynomial time. Now, what that means in more useful terms is that any problem in P can be solved in less than c*nk steps where c and k are constants, independent of the input size, n. NP on the other hand, are problems that can be solved on nondeterministic Turing machines in polynomial time. A solution to a NP problem can be verified on a deterministic Turing machine in polynomial time. The key difference is the machine type that is used, an NP problem cannot generally be solved in polynomial time on a deterministic Turing machine, it often has super-polynomial runtimes, e.g. c*kn. Again, where c and k are constants independent of the input size, n. As an example of an easy to check, but hard to find solution look at the subset sum problem, determining whether or not a subset of numbers adds to zero is easy, but picking that subset from a large group is very difficult. A prime example of the difference between P and NP problems is that of finding Eulerian and Hamiltonian circuits on a given graph. A Eulerian circuit is a path around a graph that travels across each edge just once. It can be easily solved in polynomial time b